/*
Date:20210504 16:32PM
key:都知道每次快排都能确定一个元素的下标，即锁定这个元素的位置。
    那就有三种状况，总之带着k走下去即可
*/
class Solution {
public:
void swap(int&a,int&b)
{
    if(a!=b)
    {
        a=a^b;
        b=a^b;
        a=a^b;
    }
}
    int q(vector<int>& nums, int l,int r,int const& k)
    {
        if(l>r){return 0;}
        int key=nums[l];
        int i=l;
        int j=r;
        while(i<j)
        {
            while(i<j&&nums[j]>=key){j--;}
            while(i<j&&nums[i]<=key){i++;}
            if(i<j){swap(nums[i],nums[j]);}
        }
        swap(nums[i],nums[l]);
        
        if(i==nums.size()- k){return nums[i];}
        else
        {
            if(i<nums.size()- k){return q(nums,i+1,r,k);}
            else{return q(nums,l,i-1,k);}
        }
    }
    int findKthLargest(vector<int>& nums, int k) 
    {

        return q(nums,0,nums.size()-1,k);
        
    }
};